Corelab Seminar
2014-2015
Shantanu Das (Aix-Marseille University, Marseille, France)
Symmetric Rendezvous in Graphs: Deterministic Approaches
Abstract.
We present deterministic strategies for the rendezvous of two (or more) identical agents
moving in an arbitrary connected graph. The agent move asynchronously starting from distinct vertices of the
graph and they are required to eventually meet at a single vertex of the graph. Since the agents are identical
and execute the same algorithm, rendezvousing the agents requires exploiting the asymmetry in the environment,
in terms of the structure of the graph, the graph labeling and the initial positions of the agents. Thus, in some
cases rendezvous is not realizable and we are interested in algorithms that detect the feasibility of deterministic
rendezvous in a given environment and achieve rendezvous whenever it is feasible. The techniques used for solving
Rendezvous-with-Detect depends on the capabilities of the agents (e.g. are they allowed to mark the vertices),
the prior knowledge available to the agents (e.g. an estimate of the graph size) and the optimization criteria
(e.g. whether we wish to minimize the amount of movement or the memory required for rendezvous). We will review
several such techniques that are applicable for graphs of arbitrary and unknown topologies. We will also consider
certain fault-tolerance issues.